{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #单词接龙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ladderLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词接龙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在字典（单词列表）&nbsp;<code>wordList</code> 中，从单词 <code>beginWord</code><em>&nbsp;</em>和 <code>endWord</code> 的 <strong>转换序列 </strong>是一个按下述规格形成的序列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>序列中第一个单词是 <code>beginWord</code> 。</li>\n",
    "\t<li>序列中最后一个单词是 <code>endWord</code> 。</li>\n",
    "\t<li>每次转换只能改变一个字母。</li>\n",
    "\t<li>转换过程中的中间单词必须是字典&nbsp;<code>wordList</code> 中的单词。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定两个长度相同但内容不同的单词<em> </em><code>beginWord</code><em>&nbsp;</em>和 <code>endWord</code> 和一个字典 <code>wordList</code> ，找到从&nbsp;<code>beginWord</code> 到&nbsp;<code>endWord</code> 的 <strong>最短转换序列</strong> 中的 <strong>单词数目</strong> 。如果不存在这样的转换序列，返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一个最短转换序列是 &quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;dot&quot; -&gt; &quot;dog&quot; -&gt; &quot;cog&quot;, 返回它的长度 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>endWord &quot;cog&quot; 不在字典中，所以无法进行转换。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= beginWord.length &lt;= 10</code></li>\n",
    "\t<li><code>endWord.length == beginWord.length</code></li>\n",
    "\t<li><code>1 &lt;= wordList.length &lt;= 5000</code></li>\n",
    "\t<li><code>wordList[i].length == beginWord.length</code></li>\n",
    "\t<li><code>beginWord</code>、<code>endWord</code> 和 <code>wordList[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>beginWord != endWord</code></li>\n",
    "\t<li><code>wordList</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 127&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/word-ladder/\">https://leetcode-cn.com/problems/word-ladder/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [om3reC](https://leetcode.cn/problems/om3reC/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [om3reC](https://leetcode.cn/problems/om3reC/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"hit\"\\n\"cog\"\\n[\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]', '\"hit\"\\n\"cog\"\\n[\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 将wordList转换为set以进行快速查找\n",
    "        wordSet = set(wordList)\n",
    "        \n",
    "        # 如果endWord不在wordList中，直接返回0\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "        \n",
    "        queue = [(beginWord, 1)] # 使用队列进行BFS，同时记录转换步数\n",
    "        \n",
    "        while queue:\n",
    "            word, steps = queue.pop(0)\n",
    "            \n",
    "            # 尝试替换每个字母，生成新的单词\n",
    "            for i in range(len(word)):\n",
    "                for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    newWord = word[:i] + char + word[i+1:]\n",
    "                    \n",
    "                    if newWord == endWord:  # 找到了目标单词，返回步数\n",
    "                        return steps + 1\n",
    "                    \n",
    "                    if newWord in wordSet:\n",
    "                        wordSet.remove(newWord)  # 防止重复访问\n",
    "                        queue.append((newWord, steps + 1))\n",
    "        \n",
    "        return 0  # 如果无法转换到endWord，返回0\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 将wordList转换为set以进行快速查找\n",
    "        wordSet = set(wordList)\n",
    "        \n",
    "        # 如果endWord不在wordList中，直接返回0\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "        \n",
    "        queue = [(beginWord, 1)] # 使用队列进行BFS，同时记录转换步数\n",
    "        \n",
    "        while queue:\n",
    "            word, steps = queue.pop(0)\n",
    "            \n",
    "            # 尝试替换每个字母，生成新的单词\n",
    "            for i in range(len(word)):\n",
    "                for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    newWord = word[:i] + char + word[i+1:]\n",
    "                    \n",
    "                    if newWord == endWord:  # 找到了目标单词，返回步数\n",
    "                        return steps + 1\n",
    "                    \n",
    "                    if newWord in wordSet:\n",
    "                        wordSet.remove(newWord)  # 防止重复访问\n",
    "                        queue.append((newWord, steps + 1))\n",
    "        \n",
    "        return 0  # 如果无法转换到endWord，返回0\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        ### 逻辑 BFS广度优先搜索 两个队列q1 q2 记录当前距离 和+1的距离\n",
    "        queue1 = []\n",
    "        queue2 = []\n",
    "        ### 去重\n",
    "        notvisited = set(wordList)\n",
    "        length = 1\n",
    "        queue1.append(beginWord)\n",
    "\n",
    "        def getNeighbors(word):\n",
    "            wordls = list(word)\n",
    "            neis = []\n",
    "            for i in range(len(wordls)):\n",
    "                old = wordls[i]\n",
    "                for chi in range(ord('a'), ord('z')+1):\n",
    "                    if chr(chi) != old:\n",
    "                        wordls[i] = chr(chi)\n",
    "                        newnei = ''.join(wordls)\n",
    "                        neis.append(newnei)\n",
    "                    wordls[i] = old\n",
    "            return neis\n",
    "\n",
    "\n",
    "\n",
    "        while queue1:\n",
    "            word = queue1.pop(0)\n",
    "            if word == endWord:\n",
    "                return length\n",
    "            neighbors = getNeighbors(word)\n",
    "            for nei in neighbors:\n",
    "                if nei in notvisited:\n",
    "                    queue2.append(nei)\n",
    "                    notvisited.remove(nei)\n",
    "            \n",
    "            if not queue1:\n",
    "                length += 1\n",
    "                queue1 = queue2\n",
    "                queue2 = []\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        def getNeighbor(w):\n",
    "            nonlocal wordList\n",
    "            r = []\n",
    "            for i in range(len(w)):\n",
    "                s, e = w[:i], w[i + 1:]\n",
    "                for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    c = s + j + e\n",
    "                    if c in wordList and c != w:\n",
    "                        r.append(c)\n",
    "            return r\n",
    "        \n",
    "        passed = set()\n",
    "        beginQueue, endQueue = [beginWord], [endWord]\n",
    "        beginSet, endSet = set([beginWord]), set([endWord])\n",
    "        ans = 1\n",
    "        while beginQueue and endQueue:\n",
    "            ans += 1\n",
    "            nq = []\n",
    "            for x in beginQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in endSet:\n",
    "                        return ans\n",
    "                    if y not in beginSet:\n",
    "                        beginSet.add(y)\n",
    "                        nq.append(y)\n",
    "            ans += 1\n",
    "            beginQueue = nq\n",
    "            nq = []\n",
    "            for x in endQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in beginSet:\n",
    "                        return ans\n",
    "                    if y not in endSet:\n",
    "                        endSet.add(y)\n",
    "                        nq.append(y)\n",
    "            endQueue = nq\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        q1 = deque()\n",
    "        q2 = deque()\n",
    "        no_visited = set(wordList)\n",
    "        length = 1\n",
    "        q1.append(beginWord)\n",
    "        while q1:\n",
    "            word = q1.popleft()\n",
    "            if word == endWord:\n",
    "                return length\n",
    "            neighbors = get_neighbors(word)\n",
    "            for nei in neighbors:\n",
    "                if nei in no_visited:\n",
    "                    q2.append(nei)\n",
    "                    no_visited.remove(nei)\n",
    "            if not q1:\n",
    "                length += 1\n",
    "                q1 = q2\n",
    "                q2 = deque()\n",
    "        return 0\n",
    "\n",
    "def get_neighbors(word):\n",
    "    neighbors = deque()\n",
    "    for old in range(len(word)):\n",
    "        for d in range(ord(\"a\"), ord(\"z\")+1):\n",
    "            if d != ord(word[old]):\n",
    "                neighbors.append(f\"{word[:old]}{chr(d)}{word[old+1:]}\")\n",
    "    return neighbors\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        def f(x, set3, set4, set2):\n",
    "            s = 'abcdefghijklmnopqrstuvwxyz'\n",
    "            for i in range(len(x)):\n",
    "                for j in s:\n",
    "                    if x[i] != j:\n",
    "                        w = x[:i]+j+x[i+1:]\n",
    "                        if w in set2:\n",
    "                            return True\n",
    "                        if w in set4:\n",
    "                            # print(w)\n",
    "                            set3.add(w)\n",
    "                            set4.remove(w)\n",
    "            return False\n",
    "        set1 = set([beginWord])\n",
    "        set2 = set([endWord])\n",
    "        set3 = set([])\n",
    "        set4 = set(wordList)\n",
    "        count = 2\n",
    "        # f('hit', set3, set4, set2)\n",
    "        # print(set1,set2,set3,set4)\n",
    "        # return 0\n",
    "        while set1 and set2:\n",
    "            if len(set2) < len(set1):\n",
    "                temp = set1\n",
    "                set1 = set2\n",
    "                set2 = temp\n",
    "            for word in set1:\n",
    "                if f(word, set3, set4, set2):\n",
    "                    return count\n",
    "            set1 = set3\n",
    "            set3 = set([])\n",
    "            count += 1\n",
    "            print(set1,set2)\n",
    "        return 0\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        def getNeighbor(w):\n",
    "            nonlocal wordList\n",
    "            r = []\n",
    "            for i in range(len(w)):\n",
    "                s, e = w[:i], w[i + 1:]\n",
    "                for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    c = s + j + e\n",
    "                    if c in wordList and c != w:\n",
    "                        r.append(c)\n",
    "            return r\n",
    "        \n",
    "        passed = set()\n",
    "        beginQueue, endQueue = [beginWord], [endWord]\n",
    "        beginSet, endSet = set([beginWord]), set([endWord])\n",
    "        ans = 1\n",
    "        while beginQueue and endQueue:\n",
    "            ans += 1\n",
    "            nq = []\n",
    "            for x in beginQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in endSet:\n",
    "                        return ans\n",
    "                    if y not in beginSet:\n",
    "                        beginSet.add(y)\n",
    "                        nq.append(y)\n",
    "            ans += 1\n",
    "            beginQueue = nq\n",
    "            nq = []\n",
    "            for x in endQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in beginSet:\n",
    "                        return ans\n",
    "                    if y not in endSet:\n",
    "                        endSet.add(y)\n",
    "                        nq.append(y)\n",
    "            endQueue = nq\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        word_set = set(wordList)\n",
    "        que = [beginWord]\n",
    "        level = 1\n",
    "\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            while size:\n",
    "                size -= 1\n",
    "                word = que.pop()\n",
    "                if word == endWord:\n",
    "                    return level\n",
    "                for i in range(26):\n",
    "                    for j in range(len(word)):\n",
    "                        tmp = list(word)\n",
    "                        tmp[j] = chr(ord('a') + i)\n",
    "                        tmp = ''.join(tmp)\n",
    "                        if tmp in word_set:\n",
    "                            que.insert(0, tmp)\n",
    "                            word_set.remove(tmp)\n",
    "            level += 1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        word_set = set(wordList)\n",
    "        \n",
    "        if endWord not in word_set:\n",
    "            return 0\n",
    "\n",
    "        strs = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "        left_set = {beginWord}\n",
    "        right_set = {endWord}\n",
    "\n",
    "        step = 1\n",
    "\n",
    "        while len(left_set) != 0 and len(right_set) != 0:\n",
    "            step += 1\n",
    "\n",
    "            if len(left_set) > len(right_set):\n",
    "                t = left_set\n",
    "                left_set = right_set\n",
    "                right_set = t\n",
    "\n",
    "            for w in left_set:\n",
    "                if w in word_set:\n",
    "                    word_set.remove(w)\n",
    "\n",
    "            for w in right_set:\n",
    "                if w in word_set:\n",
    "                    word_set.remove(w)\n",
    "\n",
    "            t = set()\n",
    "            for w in left_set:\n",
    "                for i in range(len(w)):\n",
    "                    for s in strs:\n",
    "                        new_word = w[:i] + s + w[i+1:]\n",
    "                        if new_word in right_set:\n",
    "                            return step\n",
    "                        if new_word not in word_set:\n",
    "                            continue\n",
    "                        t.add(new_word)\n",
    "            left_set = t\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        s = set(wordList)\n",
    "        if endWord not in s:\n",
    "            return 0\n",
    "        smallLevel, bigLevel, nextLevel = set(), set(), set()\n",
    "        smallLevel.add(beginWord)\n",
    "        bigLevel.add(endWord)\n",
    "        length = 2\n",
    "        while smallLevel:\n",
    "            length += 1\n",
    "            for w in smallLevel:\n",
    "                for j in range(len(w)):\n",
    "                    lw = list(w)\n",
    "                    for i in range(26):\n",
    "                        lw[j] = chr(97 + i)\n",
    "                        nextword = ''.join(lw)\n",
    "                        if nextword != w:\n",
    "                            if nextword in bigLevel:\n",
    "                                return length - 1\n",
    "                            if nextword in s:\n",
    "                                s.remove(nextword)\n",
    "                                nextLevel.add(nextword)\n",
    "            if len(nextLevel) <= len(bigLevel):\n",
    "                smallLevel = nextLevel.copy()\n",
    "            else:\n",
    "                tmp = nextLevel.copy()\n",
    "                smallLevel = bigLevel.copy()\n",
    "                bigLevel = tmp.copy()\n",
    "            nextLevel.clear()\n",
    "        return 0\n",
    "        \n",
    "                     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "#         ### 单向搜索 逻辑 BFS广度优先搜索 两个队列q1 q2 记录当前距离 和+1的距离\n",
    "#         queue1 = []\n",
    "#         queue2 = []\n",
    "#         ### 去重\n",
    "#         notvisited = set(wordList)\n",
    "#         length = 1\n",
    "#         queue1.append(beginWord)\n",
    "\n",
    "#         def getNeighbors(word):\n",
    "#             wordls = list(word)\n",
    "#             neis = []\n",
    "#             for i in range(len(wordls)):\n",
    "#                 old = wordls[i]\n",
    "#                 for chi in range(ord('a'), ord('z')+1):\n",
    "#                     if chr(chi) != old:\n",
    "#                         wordls[i] = chr(chi)\n",
    "#                         newnei = ''.join(wordls)\n",
    "#                         neis.append(newnei)\n",
    "#                     wordls[i] = old\n",
    "#             return neis\n",
    "\n",
    "\n",
    "\n",
    "#         while queue1:\n",
    "#             word = queue1.pop(0)\n",
    "#             if word == endWord:\n",
    "#                 return length\n",
    "#             neighbors = getNeighbors(word)\n",
    "#             for nei in neighbors:\n",
    "#                 if nei in notvisited:\n",
    "#                     queue2.append(nei)\n",
    "#                     notvisited.remove(nei)\n",
    "            \n",
    "#             if not queue1:\n",
    "#                 length += 1\n",
    "#                 queue1 = queue2\n",
    "#                 queue2 = []\n",
    "\n",
    "#         return 0\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        ### 双向搜索 逻辑 \n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        def getNeighbors(word):\n",
    "            wordls = list(word)\n",
    "            neis = []\n",
    "            for i in range(len(wordls)):\n",
    "                old = wordls[i]\n",
    "                for chi in range(ord('a'), ord('z')+1):\n",
    "                    if chr(chi) != old:\n",
    "                        wordls[i] = chr(chi)\n",
    "                        newnei = ''.join(wordls)\n",
    "                        neis.append(newnei)\n",
    "                    wordls[i] = old\n",
    "            return neis\n",
    "\n",
    "        notvisited = set(wordList)\n",
    "        set1 = set()\n",
    "        set2 = set()\n",
    "        length = 2\n",
    "        set1.add(beginWord)\n",
    "        set2.add(endWord)\n",
    "        notvisited.remove(endWord)\n",
    "        while set1 and set2:\n",
    "            if len(set1) > len(set2):\n",
    "                set1, set2 = set2, set1\n",
    "            set3 = set()\n",
    "            for word in set1:\n",
    "                neighbors = getNeighbors(word)\n",
    "                for nei in neighbors:\n",
    "                    if nei in set2:\n",
    "                        return length\n",
    "                    if nei in notvisited:\n",
    "                        notvisited.remove(nei)\n",
    "                        set3.add(nei)\n",
    "            length += 1\n",
    "            set1 = set3\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        def getNeighbor(w):\n",
    "            nonlocal wordList\n",
    "            r = []\n",
    "            for i in range(len(w)):\n",
    "                s, e = w[:i], w[i + 1:]\n",
    "                for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    c = s + j + e\n",
    "                    if c in wordList and c != w:\n",
    "                        r.append(c)\n",
    "            return r\n",
    "        \n",
    "        passed = set()\n",
    "        beginQueue, endQueue = [beginWord], [endWord]\n",
    "        beginSet, endSet = set([beginWord]), set([endWord])\n",
    "        ans = 1\n",
    "        while beginQueue and endQueue:\n",
    "            ans += 1\n",
    "            nq = []\n",
    "            for x in beginQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in endSet:\n",
    "                        return ans\n",
    "                    if y not in beginSet:\n",
    "                        beginSet.add(y)\n",
    "                        nq.append(y)\n",
    "            ans += 1\n",
    "            beginQueue = nq\n",
    "            print(\"b: \" + str(nq))\n",
    "            nq = []\n",
    "            for x in endQueue:\n",
    "                for y in getNeighbor(x):\n",
    "                    if y in beginSet:\n",
    "                        return ans\n",
    "                    if y not in endSet:\n",
    "                        endSet.add(y)\n",
    "                        nq.append(y)\n",
    "            endQueue = nq\n",
    "            print(\"e: \" + str(nq))\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        wordSet = set(wordList)\n",
    "\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "\n",
    "        f_queue = [(beginWord, 0)]\n",
    "        f_vis = {beginWord: 0}\n",
    "\n",
    "        b_queue = [(endWord, 1)]\n",
    "        b_vis = {endWord: 1}\n",
    "\n",
    "        while f_queue and b_queue:\n",
    "            if len(f_queue) <= len(b_queue):\n",
    "                cur, step = f_queue.pop(0)\n",
    "                queue = f_queue\n",
    "                vis = f_vis\n",
    "                otherVis = b_vis\n",
    "\n",
    "            else:\n",
    "                cur, step = b_queue.pop(0)\n",
    "                queue = b_queue\n",
    "                vis = b_vis\n",
    "                otherVis = f_vis\n",
    "\n",
    "            if cur in otherVis:\n",
    "                return step + otherVis[cur]\n",
    "\n",
    "            for i in range(len(cur)):\n",
    "                for j in range(26):\n",
    "                    if j + 97 != ord(cur[i]):\n",
    "                        newWord = cur[:i] + chr(j + 97) + cur[i + 1:]\n",
    "                        if newWord not in vis and newWord in wordSet:\n",
    "                            vis[newWord] = step + 1\n",
    "                            queue.append((newWord, step + 1))\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        word_set = set(wordList)\n",
    "        que = [beginWord]\n",
    "        level = 1\n",
    "\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            while size:\n",
    "                size -= 1\n",
    "                word = que.pop()\n",
    "                if word == endWord:\n",
    "                    return level\n",
    "                for i in range(len(word)):\n",
    "                    for j in range(26):\n",
    "                        tmp = list(word)\n",
    "                        tmp[i] = chr(ord('a') + j)\n",
    "                        tmp = ''.join(tmp)\n",
    "                        if tmp in word_set:\n",
    "                            que.insert(0, tmp)\n",
    "                            word_set.remove(tmp)\n",
    "            level += 1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # def edge(s, t):\n",
    "        #     k = 0\n",
    "        #     for i in range(len(s)):\n",
    "        #         if s[i] != t[i]:\n",
    "        #             k += 1\n",
    "        #         if k == 2:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        # wordList.append(beginWord)\n",
    "        # n = len(wordList)\n",
    "        # graph = defaultdict(list)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if edge(wordList[i], wordList[j]):\n",
    "        #             graph[wordList[i]].append(wordList[j])\n",
    "        #             graph[wordList[j]].append(wordList[i])\n",
    "        # q = deque([(beginWord, 1)])\n",
    "        # visited = set([beginWord])\n",
    "        # while q:\n",
    "        #     x, l = q.popleft()\n",
    "        #     if x == endWord:\n",
    "        #         return l\n",
    "        #     for y in graph[x]:\n",
    "        #         if y not in visited:\n",
    "        #             visited.add(y)\n",
    "        #             q.append((y, l+1))\n",
    "        # return 0\n",
    "        wordList = set(wordList)\n",
    "        q = deque([(beginWord, 1)])\n",
    "        visited = set([beginWord])\n",
    "        while q:\n",
    "            x, l = q.popleft()\n",
    "            if x == endWord:\n",
    "                return l\n",
    "            for i in range(len(x)):\n",
    "                for j in list('abcdefghijklmnopqrstuvwxyz'):\n",
    "                    y = x[:i]+j+x[i+1:]\n",
    "                    if y not in visited and y in wordList:\n",
    "                        visited.add(y)\n",
    "                        q.append((y, l+1))\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 将wordList转换为set以进行快速查找\n",
    "        wordSet = set(wordList)\n",
    "        \n",
    "        # 如果endWord不在wordList中，直接返回0\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "        \n",
    "        queue = [(beginWord, 1)] # 使用队列进行BFS，同时记录转换步数\n",
    "        \n",
    "        while queue:\n",
    "            word, steps = queue.pop(0)\n",
    "            \n",
    "            # 尝试替换每个字母，生成新的单词\n",
    "            for i in range(len(word)):\n",
    "                for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    newWord = word[:i] + char + word[i+1:]\n",
    "                    \n",
    "                    if newWord == endWord:  # 找到了目标单词，返回步数\n",
    "                        return steps + 1\n",
    "                    \n",
    "                    if newWord in wordSet:\n",
    "                        wordSet.remove(newWord)  # 防止重复访问\n",
    "                        queue.append((newWord, steps + 1))\n",
    "        \n",
    "        return 0  # 如果无法转换到endWord，返回0\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        \n",
    "        def cj(w1,w2):\n",
    "            c=0\n",
    "            if len(w1)!=len(w2):return inf\n",
    "            for i in  range(len(w1)):\n",
    "                if w1[i]!=w2[i]:\n",
    "                    c+=1\n",
    "            return c\n",
    "\n",
    "        que=[beginWord]\n",
    "        wordListSet=set(wordList)\n",
    "        c=0\n",
    "        wdlen=len(beginWord)\n",
    "        while(que):\n",
    "            c+=1\n",
    "            nq=[]\n",
    "            for wd in que:\n",
    "                for i in range(wdlen):\n",
    "                    wdlist=list(wd)\n",
    "                    for j in range(26):\n",
    "\n",
    "                        wdlist[i]=chr( ord('a')+j)\n",
    "                        nwd=''.join(wdlist)\n",
    "                        if nwd in wordListSet:\n",
    "                            wordListSet.remove(nwd)\n",
    "                            nq.append(nwd)\n",
    "                            if nwd==endWord:\n",
    "                                return c+1\n",
    "\n",
    "            que=nq\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        visited = {ii:False for ii in wordList}\n",
    "        from collections import deque\n",
    "        Q = deque()\n",
    "        Q.append(beginWord)\n",
    "        visited[beginWord] = True\n",
    "        len_word = len(beginWord)\n",
    "        st=set(wordList)#判断word_now是否在list里面会超时，set比list更高效！！\n",
    "        step = 1\n",
    "        while Q:#单层for 下面有双层for\n",
    "            len_ = len(Q)\n",
    "            for _ in range(len_):\n",
    "                now_word = Q.popleft()\n",
    "                for i in range(len_word):##选哪一位\n",
    "                    for j in range(26):#ord chr #该位如何改变\n",
    "                        tmp = now_word[:i]+chr(97+j)+now_word[i+1:]\n",
    "                        if tmp in st and visited[tmp]==False:\n",
    "                            if tmp == endWord:\n",
    "                                return step+1\n",
    "                            visited[tmp] = True\n",
    "                            Q.append(tmp)\n",
    "            step += 1\n",
    "        return 0\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        visited = {ii:False for ii in wordList}\n",
    "        from collections import deque\n",
    "        Q = deque()\n",
    "        Q.append(beginWord)\n",
    "        visited[beginWord] = True\n",
    "        len_word = len(beginWord)\n",
    "        step = 1\n",
    "        st=set(wordList)\n",
    "        while Q:\n",
    "            len_ = len(Q)\n",
    "            for _ in range(len_):\n",
    "                now_word = Q.popleft()\n",
    "                for i in range(len_word):\n",
    "                    for j in range(26):#ord chr\n",
    "                        tmp = now_word[:i]+chr(97+j)+now_word[i+1:]\n",
    "                        if tmp in st and visited[tmp]==False:\n",
    "                            if tmp == endWord:\n",
    "                                return step+1\n",
    "                            visited[tmp] = True\n",
    "                            Q.append(tmp)\n",
    "            step+=1\n",
    "        return 0\n",
    "'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # write your code here\n",
    "        # * 结果可能不出现在dict\n",
    "        if not wordList or endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        # * 去重\n",
    "        wordList = set(wordList)\n",
    "        queue = [beginWord]\n",
    "        visited = set()\n",
    "        visited.add(beginWord)\n",
    "        distance = 0\n",
    "        while queue:\n",
    "            distance += 1\n",
    "            for _ in range(len(queue)):\n",
    "                # 终止条件\n",
    "                current_word = queue.pop(0)\n",
    "                if current_word == endWord:\n",
    "                    return distance\n",
    "                \n",
    "                # 入队: 只有满足 每次只能改变一个字母 & 过程中的中间单词必须在字典中出现。 才能作为候选\n",
    "                for next_word in self.get_next_words(current_word, wordList):\n",
    "                    if next_word in visited:\n",
    "                        continue\n",
    "                    visited.add(next_word)\n",
    "                    queue.append(next_word)\n",
    "            \n",
    "        return 0\n",
    "\n",
    "    def get_next_words(self, current_word, dict):\n",
    "        \"\"\"\n",
    "        每次只能改变一个字母 & 过程中的中间单词必须在字典中出现。 才能作为候选\n",
    "        \"\"\"\n",
    "        next_words = []\n",
    "        for i in range(len(current_word)):\n",
    "            left =  current_word[:i]\n",
    "            right = current_word[i+1:]\n",
    "            for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if char == current_word[i]:\n",
    "                    continue\n",
    "                select_word = left + char + right\n",
    "                if select_word in dict:\n",
    "                    next_words.append(select_word)\n",
    "        \n",
    "        return next_words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 将wordList转换为set以进行快速查找\n",
    "        wordSet = set(wordList)\n",
    "        \n",
    "        # 如果endWord不在wordList中，直接返回0\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "        \n",
    "        queue = deque([(beginWord, 1)])  # 使用队列进行BFS，同时记录转换步数\n",
    "        \n",
    "        while queue:\n",
    "            word, steps = queue.popleft()\n",
    "            \n",
    "            # 尝试替换每个字母，生成新的单词\n",
    "            for i in range(len(word)):\n",
    "                for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    newWord = word[:i] + char + word[i+1:]\n",
    "                    \n",
    "                    if newWord == endWord:  # 找到了目标单词，返回步数\n",
    "                        return steps + 1\n",
    "                    \n",
    "                    if newWord in wordSet:\n",
    "                        wordSet.remove(newWord)  # 防止重复访问\n",
    "                        queue.append((newWord, steps + 1))\n",
    "        \n",
    "        return 0  # 如果无法转换到endWord，返回0\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        st = set(wordList)\n",
    "        if endWord not in st:\n",
    "            return 0\n",
    "\n",
    "        q = deque([(beginWord, 1)])\n",
    "        vis = {beginWord, }\n",
    "        while q:\n",
    "            w, dis = q.popleft()\n",
    "            if w == endWord:\n",
    "                return dis\n",
    "            for i in range(len(w)):\n",
    "                nxt, ch = list(w), w[i]\n",
    "                for c in ascii_lowercase:\n",
    "                    if c == ch:\n",
    "                        continue\n",
    "                    nxt[i] = c\n",
    "                    if \"\".join(nxt) in st and \"\".join(nxt) not in vis:\n",
    "                        vis.add(\"\".join(nxt))\n",
    "                        q.append((\"\".join(nxt), dis + 1))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        ss = set(wordList)\n",
    "        vis = set()\n",
    "        if endWord not in ss:return 0\n",
    "        q = deque([beginWord])\n",
    "        vis.add(beginWord)\n",
    "        m = len(beginWord)\n",
    "        t = 0\n",
    "        while q:\n",
    "            t += 1\n",
    "            for _ in range(len(q)):\n",
    "                wo = q.popleft()\n",
    "                if wo == endWord:return t\n",
    "                for i in range(m):\n",
    "                    for j in range(26):\n",
    "                        if wo[:i]+chr(97+j)+wo[i+1:] in ss and wo[:i]+chr(97+j)+wo[i+1:] not in vis:\n",
    "                            q.append(wo[:i]+chr(97+j)+wo[i+1:])\n",
    "                            vis.add(wo[:i]+chr(97+j)+wo[i+1:])\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "    def ladderLength(self,beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 将 wordList 转换为 set，加速单词的查找\n",
    "        wordSet = set(wordList)\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "\n",
    "        # 初始化队列和 visited 集合\n",
    "        queue = deque([(beginWord, 1)])\n",
    "        visited = set()\n",
    "\n",
    "        # 开始 BFS\n",
    "        while queue:\n",
    "            word, level = queue.popleft()\n",
    "            if word == endWord:\n",
    "                return level\n",
    "            for i in range(len(word)):\n",
    "                for c in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "                    newWord = word[:i] + c + word[i+1:]\n",
    "                    if newWord in wordSet and newWord not in visited:\n",
    "                        queue.append((newWord, level+1))\n",
    "                        visited.add(newWord)\n",
    "                        wordSet.remove(newWord)\n",
    "\n",
    "        # 如果无法到达 endWord，则返回 0\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 正常思路：傻逼力扣不给过超时\n",
    "        # from collections import deque\n",
    "        # if endWord not in wordList:\n",
    "        #     return 0\n",
    "        # res = 1\n",
    "        # queue = []\n",
    "        # def check(w1,w2):\n",
    "        #     diff = 0 \n",
    "        #     for idx in range(len(w1)):\n",
    "        #         if w1[idx] != w2[idx]:\n",
    "        #             diff +=1\n",
    "        #             if diff > 1:\n",
    "        #                 return False\n",
    "        #     return diff == 1\n",
    "        # queue = deque()\n",
    "        # for word in wordList:\n",
    "        #     if check(word,beginWord):\n",
    "        #         queue.append(word)\n",
    "        # visited = set()\n",
    "        # while queue:\n",
    "        #     res += 1\n",
    "        #     for i in range(len(queue)):\n",
    "        #         word = queue.popleft()\n",
    "        #         visited.add(word)\n",
    "        #         if word == endWord:\n",
    "        #             return res \n",
    "        #         for w in wordList:\n",
    "        #             if w not in visited :\n",
    "        #                 diff = 0 \n",
    "        #                 for idx in range(len(w)):\n",
    "        #                     if w[idx] != word[idx]:\n",
    "        #                         diff +=1\n",
    "        #                         if diff > 1:\n",
    "        #                             break\n",
    "        #                 if diff == 1:\n",
    "        #                     queue.append(w)\n",
    "        # return 0\n",
    "        from collections import deque\n",
    "        word_set = set(wordList)\n",
    "        if endWord not in word_set:\n",
    "            return 0\n",
    "        if beginWord in word_set:\n",
    "            word_set.remove(beginWord)\n",
    "        q = deque()\n",
    "        q.append(beginWord)\n",
    "        visited = {beginWord}\n",
    "        dist = 1\n",
    "        while q:\n",
    "            dist += 1\n",
    "            for _ in range(len(q)):\n",
    "                curr_word = q.popleft()\n",
    "                for i in range(len(curr_word)):\n",
    "                    for j in range(26):\n",
    "                        word = curr_word[:i] + chr(ord('a') + j) + curr_word[i+1:]\n",
    "                        if word == endWord:\n",
    "                            return dist\n",
    "                        if word in word_set and word not in visited:\n",
    "                            q.append(word)\n",
    "                            visited.add(word)\n",
    "        return 0\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # write your code here\n",
    "        # * 结果可能不出现在dict\n",
    "        if not wordList or endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        # * 去重\n",
    "        wordList = set(wordList)\n",
    "        queue = [beginWord]\n",
    "        visited = set()\n",
    "        visited.add(beginWord)\n",
    "        distance = 0\n",
    "        while queue:\n",
    "            distance += 1\n",
    "            for _ in range(len(queue)):\n",
    "                # 终止条件\n",
    "                current_word = queue.pop(0)\n",
    "                if current_word == endWord:\n",
    "                    return distance\n",
    "                \n",
    "                # 入队: 只有满足 每次只能改变一个字母 & 过程中的中间单词必须在字典中出现。 才能作为候选\n",
    "                for next_word in self.get_next_words(current_word, wordList):\n",
    "                    if next_word in visited:\n",
    "                        continue\n",
    "                    visited.add(next_word)\n",
    "                    queue.append(next_word)\n",
    "            \n",
    "        return 0\n",
    "\n",
    "    def get_next_words(self, current_word, dict):\n",
    "        \"\"\"\n",
    "        每次只能改变一个字母 & 过程中的中间单词必须在字典中出现。 才能作为候选\n",
    "        \"\"\"\n",
    "        next_words = []\n",
    "        for i in range(len(current_word)):\n",
    "            left =  current_word[:i]\n",
    "            right = current_word[i+1:]\n",
    "            for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if char == current_word[i]:\n",
    "                    continue\n",
    "                select_word = left + char + right\n",
    "                if select_word in dict:\n",
    "                    next_words.append(select_word)\n",
    "        \n",
    "        return next_words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        queue = [(beginWord, 1)]\n",
    "        vis = {beginWord}\n",
    "        lens = len(beginWord)\n",
    "        wordSet = set(wordList)\n",
    "\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "\n",
    "        while queue:\n",
    "            cur, step = queue.pop(0)\n",
    "\n",
    "            if cur == endWord:\n",
    "                return step\n",
    "\n",
    "            for i in range(lens):\n",
    "                for c in range(26):\n",
    "                    if c + 97 != ord(cur[i]):\n",
    "                        newWord = cur[:i] + chr(c + 97) + cur[i + 1:]\n",
    "                        if newWord in wordSet and newWord not in vis:\n",
    "                            vis.add(newWord)\n",
    "                            queue.append((newWord, step + 1))\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordSet = set(wordList)\n",
    "\n",
    "        if len(wordSet) == 0 or endWord not in wordSet:\n",
    "            return 0 \n",
    "        \n",
    "        wordMap = dict()\n",
    "        wordMap[beginWord] = 1\n",
    "\n",
    "        queue = []\n",
    "        queue.append(beginWord)\n",
    "        while queue:\n",
    "            word = queue.pop(0)\n",
    "            step = wordMap[word]\n",
    "            for i in range(len(word)):\n",
    "                strs = list(word)\n",
    "                for j in range(26):\n",
    "                    strs[i] = chr(ord(\"a\") + j)\n",
    "                    new = \"\".join(strs)\n",
    "                    if new == endWord:\n",
    "                        return step + 1\n",
    "                    if new in wordSet and new not in wordMap:\n",
    "                        wordMap[new] = step + 1\n",
    "                        queue.append(new)\n",
    "        \n",
    "        return 0 \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 最短路径，广搜，到达终点一定是最短路\n",
    "        # 无向图，需要用标记位置，是否走过，否则死循环\n",
    "        wordSet = set(wordList)\n",
    "        if len(wordList)==0 or endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        mapping = {beginWord:1} #记录每个单词的最短路\n",
    "        queue = deque([beginWord])\n",
    "        while queue:\n",
    "            word = queue.popleft() #弹出队首\n",
    "            path = mapping[word]\n",
    "            for i in range(len(word)):#每个单词的长度对应一种可能你\n",
    "                word_list = list(word)\n",
    "                for j in range(26):#有26个字母\n",
    "                    word_list[i] = chr(ord('a')+j)\n",
    "                    newWord = \"\".join(word_list) #得到新单词\n",
    "                    if newWord == endWord:\n",
    "                        return path+1 #到达最短路\n",
    "                    if newWord in wordSet and newWord not in mapping:#这里注意，新单词在wordser但是没有在mapping里面\n",
    "                        mapping[newWord] = path+1 #记录每个单词的最短路\n",
    "                        queue.append(newWord)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordSet = set(wordList)\n",
    "        if endWord not in wordSet:\n",
    "            return 0\n",
    "        \n",
    "        q = deque([(beginWord, 1)])\n",
    "        visited = set([beginWord])\n",
    "        \n",
    "        while q:\n",
    "            word, length = q.popleft()\n",
    "            if word == endWord:\n",
    "                return length\n",
    "            \n",
    "            for i in range(len(word)):\n",
    "                for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                    next_word = word[:i] + c + word[i+1:]\n",
    "                    if next_word in wordSet and next_word not in visited:\n",
    "                        q.append((next_word, length + 1))\n",
    "                        visited.add(next_word)\n",
    "        \n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # endWord不在wordList直接返回\n",
    "        try:\n",
    "            endi = wordList.index(endWord) + 1\n",
    "        except:\n",
    "            return 0\n",
    "\n",
    "        N = len(wordList)\n",
    "\n",
    "        # 检查两单词能否一次转换\n",
    "        def check(w1, w2):\n",
    "            num = 0\n",
    "            for c1, c2 in zip(w1, w2):\n",
    "                num += c1 != c2\n",
    "                if num == 2:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 记录每个单词的下一个，beginWord为0，其他为序号+1\n",
    "        l_next = [[] for _ in range(N + 1)]\n",
    "\n",
    "        for i, w1 in enumerate(wordList, 1):\n",
    "            now = l_next[i]\n",
    "\n",
    "            if check(w1, beginWord):\n",
    "                now.append(0)\n",
    "                l_next[0].append(i)\n",
    "\n",
    "            for j in range(i, N):\n",
    "                if check(w1, wordList[j]):\n",
    "                    now.append(j + 1)\n",
    "                    l_next[j + 1].append(i)\n",
    "\n",
    "        # 每个单词的距离\n",
    "        l_jl = [0] * (N + 1)\n",
    "        l_jl[0] = 1\n",
    "\n",
    "        # 从beginWord开始BFS\n",
    "        dp = [0]\n",
    "\n",
    "        while dp:\n",
    "            f = dp.pop(0)\n",
    "            jl = l_jl[f] + 1\n",
    "\n",
    "            for t in l_next[f]:\n",
    "                if t == endi:\n",
    "                    return jl\n",
    "\n",
    "                if l_jl[t] == 0:\n",
    "                    l_jl[t] = jl\n",
    "                    dp.append(t)\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordset = set(wordList)\n",
    "        queue = collections.deque([beginWord])\n",
    "        if len(wordset)== 0 or endWord not in wordset:\n",
    "            return 0\n",
    "        mapping = {beginWord:1}\n",
    "        while queue:\n",
    "            word = queue.popleft()\n",
    "            path = mapping[word]\n",
    "            print(word)\n",
    "            for i in range(len(word)):\n",
    "                word_list = list(word)\n",
    "                for j in range(26):\n",
    "                    word_list[i]=chr(ord(\"a\")+j)\n",
    "                    new_word = \"\".join(word_list)\n",
    "                    if new_word==endWord:\n",
    "                        return path+1\n",
    "                    if new_word in wordset and new_word not in mapping:\n",
    "                        mapping[new_word] = path+1\n",
    "                        queue.append(new_word)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:\n",
    "        n = len(wordList)\n",
    "        q = deque()\n",
    "        mp = dict()\n",
    "        vis = dict()\n",
    "        seen = set(wordList)\n",
    "        res = []\n",
    "        q.append(beginWord)\n",
    "\n",
    "\n",
    "        if endWord not in seen:\n",
    "            return 0\n",
    "\n",
    "        match = False\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            if s == endWord:\n",
    "                match = True\n",
    "                break\n",
    "            \n",
    "            for i in range(len(s)):\n",
    "                for c in ascii_lowercase:\n",
    "                    t = s[:i] + c + s[i+1:]\n",
    "                    if t in seen and t not in vis:\n",
    "                        vis[t] = True\n",
    "                        q.append(t)\n",
    "                        mp[t] = s\n",
    "\n",
    "        if not match:\n",
    "            return 0\n",
    "        \n",
    "\n",
    "        s = endWord\n",
    "        while s != beginWord:\n",
    "            res.append(s)\n",
    "            s = mp[s]\n",
    "        res.append(beginWord)\n",
    "        return len(res)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        def check(s1, s2):\n",
    "            flag = False\n",
    "            for i in range(m):\n",
    "                if s1[i] != s2[i]:\n",
    "                    if not flag:\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        return False\n",
    "            return flag\n",
    "\n",
    "        n = len(wordList)\n",
    "        graph = {word:[] for word in wordList}\n",
    "        m = len(beginWord)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if check(wordList[i], wordList[j]):\n",
    "                    graph[wordList[i]].append(wordList[j])\n",
    "                    graph[wordList[j]].append(wordList[i])\n",
    "        graph[beginWord] = []\n",
    "        for i in range(n):\n",
    "            if check(beginWord, wordList[i]):\n",
    "                graph[beginWord].append(wordList[i])\n",
    "\n",
    "\n",
    "        q = [beginWord]\n",
    "        count = 1\n",
    "        visited = set()\n",
    "        while q:\n",
    "            print(q)\n",
    "            count += 1\n",
    "            nxt = []\n",
    "            for cur in q:\n",
    "                for word in graph[cur]:\n",
    "                    if word == endWord:\n",
    "                        return count\n",
    "                    if word not in visited:\n",
    "                        visited.add(word)\n",
    "                        nxt.append(word)\n",
    "            q = nxt\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def similar(word1, word2):\n",
    "            cnt = 0\n",
    "            for i in range(len(word1)):\n",
    "                if word1[i] != word2[i]:\n",
    "                    if cnt > 0:\n",
    "                        return False\n",
    "                    cnt = 1 \n",
    "            return cnt == 1\n",
    "\n",
    "        n = len(wordList)\n",
    "        unvisited = set()\n",
    "        exists = False\n",
    "        for i in range(n):\n",
    "            unvisited.add(i)\n",
    "            if not exists and endWord == wordList[i]:\n",
    "                exists = True\n",
    "        if not exists:\n",
    "            return 0\n",
    "        q = queue.Queue()\n",
    "        q.put(beginWord)\n",
    "        level = 1\n",
    "        while not q.empty():\n",
    "            size = q.qsize()\n",
    "            temp = set(unvisited)\n",
    "            for _ in range(size):\n",
    "                prev = q.get()\n",
    "                for i in unvisited:\n",
    "                    if similar(prev, wordList[i]):\n",
    "                        if wordList[i] == endWord:\n",
    "                            return level + 1\n",
    "                        temp.remove(i)\n",
    "                        q.put(wordList[i])\n",
    "                unvisited = set(temp)\n",
    "            level += 1\n",
    "        \n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def edge(s, t):\n",
    "            k = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != t[i]:\n",
    "                    k += 1\n",
    "                if k == 2:\n",
    "                    return False\n",
    "            return True\n",
    "        wordList.append(beginWord)\n",
    "        n = len(wordList)\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if edge(wordList[i], wordList[j]):\n",
    "                    graph[wordList[i]].append(wordList[j])\n",
    "                    graph[wordList[j]].append(wordList[i])\n",
    "        q = deque([(beginWord, 1)])\n",
    "        visited = set([beginWord])\n",
    "        while q:\n",
    "            x, l = q.popleft()\n",
    "            if x == endWord:\n",
    "                return l\n",
    "            for y in graph[x]:\n",
    "                if y not in visited:\n",
    "                    visited.add(y)\n",
    "                    q.append((y, l+1))\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        def can_be_tansp(word1,word2):\n",
    "            difference = 0\n",
    "            for i,j in zip(word1,word2):\n",
    "                if i != j:\n",
    "                    difference += 1\n",
    "                    if difference == 2:\n",
    "                        return False\n",
    "            return True\n",
    "        n = len(wordList)\n",
    "        mapdict = {beginWord:[]}\n",
    "        for word in wordList:\n",
    "            if can_be_tansp(beginWord,word):\n",
    "                mapdict[beginWord].append(word)\n",
    "        for i,word1 in enumerate(wordList):\n",
    "            for word2 in wordList[i + 1:]:\n",
    "                if can_be_tansp(word1, word2):\n",
    "                    if word1 in mapdict:\n",
    "                        mapdict[word1].append(word2)\n",
    "                    else:\n",
    "                        mapdict[word1] = [word2]\n",
    "                    if word2 in mapdict:\n",
    "                        mapdict[word2].append(word1)\n",
    "                    else:\n",
    "                        mapdict[word2] = [word1]\n",
    "        ans = 0\n",
    "        dequelist = deque()\n",
    "        dequelist.append(beginWord)\n",
    "        colseset = set()\n",
    "\n",
    "        while dequelist:\n",
    "            nowlen = len(dequelist)\n",
    "            ans += 1\n",
    "            for i in range(nowlen):\n",
    "                nowword = dequelist.popleft()\n",
    "                if nowword == endWord:\n",
    "                    return ans\n",
    "                if nowword not in colseset:\n",
    "                    dequelist += mapdict[nowword]\n",
    "                colseset.add(nowword)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def isConnect(s1, s2):\n",
    "            diff = 0\n",
    "            for w1, w2 in zip(s1, s2):\n",
    "                if w1 != w2:\n",
    "                    diff += 1\n",
    "                if diff > 1:\n",
    "                    return False\n",
    "            return diff == 1\n",
    "\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        if beginWord not in wordList:\n",
    "            wordList = [beginWord] + wordList\n",
    "        else:\n",
    "            wl = set(wordList)\n",
    "            wl.remove(beginWord)\n",
    "            wordList = [beginWord] + list(wl)\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for i, w in enumerate(wordList):\n",
    "            for j in range(i + 1, len(wordList)):\n",
    "                if isConnect(w, wordList[j]):\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "        \n",
    "        st = deque([[0, 0]])\n",
    "        visted = set([0])\n",
    "        while st:\n",
    "            cur, dep = st.popleft()\n",
    "            if wordList[cur] == endWord:\n",
    "                return dep + 1\n",
    "            for adj in graph[cur]:\n",
    "                if adj not in visted:\n",
    "                    st.append([adj, dep + 1])\n",
    "                visted.add(adj)\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        all_states = {}\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                state = word[:i] + \"*\" + word[i + 1:]\n",
    "                if state not in all_states:\n",
    "                    all_states[state] = [word]\n",
    "                else:\n",
    "                    all_states[state].append(word)\n",
    "        q, head = [beginWord], -1\n",
    "        visited = set(q)\n",
    "        num_steps = [1]\n",
    "        while head < len(q) - 1:\n",
    "            head += 1\n",
    "            for i in range(len(q[head])):\n",
    "                state = q[head][:i] + \"*\" + q[head][i + 1:]\n",
    "                if state not in all_states:\n",
    "                    continue\n",
    "                for word in all_states[state]:\n",
    "                    if word not in visited:\n",
    "                        if word == endWord:\n",
    "                            return num_steps[head] + 1\n",
    "                        q.append(word)\n",
    "                        visited.add(word)\n",
    "                        num_steps.append(num_steps[head] + 1)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList) -> int:\n",
    "        now=[beginWord]+wordList\n",
    "        arr={}\n",
    "        yep=0\n",
    "        for i in now:\n",
    "            if i==endWord:\n",
    "                yep=1\n",
    "            for j in range(len(i)):\n",
    "                k=i[0:j]+'*'+i[j+1:]\n",
    "                if k in arr:\n",
    "                    arr[k].append(i)\n",
    "                else:\n",
    "                    arr[k]=[i]\n",
    "        if yep==0:\n",
    "            return 0\n",
    "        ifused= {}\n",
    "        for j in now:\n",
    "            ifused[j]=0\n",
    "        ifused[beginWord]=1\n",
    "        lis1=deque()\n",
    "        lis2=deque()\n",
    "        lis1.append(beginWord)\n",
    "        num=2\n",
    "        while len(lis1) or len(lis2):\n",
    "            if len(lis1)==0:\n",
    "                lis1=lis2.copy()\n",
    "                lis2.clear()\n",
    "                num+=1\n",
    "            new=lis1.pop()\n",
    "            for i in range(len(new)):\n",
    "                k=new[0:i]+'*'+new[i+1:]\n",
    "                for j in arr[k]:\n",
    "                    if j==endWord:\n",
    "                        return num\n",
    "                    if ifused[j]==0:\n",
    "                        lis2.append(j)\n",
    "                        ifused[j]=1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        wordList=[beginWord]+wordList+[endWord]\n",
    "        from collections import defaultdict\n",
    "        g=defaultdict(set)\n",
    "        def rem(s,ind):\n",
    "            return s[:ind]+s[ind+1:]\n",
    "        for i in range(len(beginWord)):\n",
    "            ma=defaultdict(list)\n",
    "            for j in range(len(wordList)):\n",
    "                ma[rem(wordList[j],i)].append(j)\n",
    "            for j in ma.values():\n",
    "                for k in range(len(j)):\n",
    "                    for l in range(len(j)):\n",
    "                        if l!=k:\n",
    "                            g[j[l]].add(j[k])\n",
    "        q=[0]\n",
    "        qi=0\n",
    "        last=[-1]*len(wordList)\n",
    "        last[0]=-2\n",
    "        while qi<len(q):\n",
    "            x=q[qi]\n",
    "            qi+=1\n",
    "            for to in g[x]:\n",
    "                if last[to]==-1:\n",
    "                    last[to]=x\n",
    "                    q.append(to)\n",
    "                    if to==len(wordList)-1:\n",
    "                        break\n",
    "            if last[-1]!=-1:\n",
    "                break\n",
    "        if last[-1]==-1:\n",
    "            return 0\n",
    "        p=[]\n",
    "        i=to\n",
    "\n",
    "        while i>=0:\n",
    "            p.append(i)\n",
    "            i=last[i]\n",
    "        return len(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                hashmap[word[:i] + '*' + word[i+1:]].append(word)\n",
    "        q = collections.deque([beginWord])\n",
    "        w_dict = {beginWord:[beginWord]}\n",
    "\n",
    "        while q:\n",
    "            word = q.popleft()\n",
    "            if word == endWord:\n",
    "                return len(w_dict[word])\n",
    "            for i in range(len(word)):\n",
    "                if word[:i] + '*' + word[i+1:] in hashmap:\n",
    "                    for tmp in hashmap[word[:i] + '*' + word[i+1:]]:\n",
    "                        if tmp not in w_dict:\n",
    "                            w_dict[tmp] = w_dict[word] + [tmp]\n",
    "                            q.append(tmp)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                hashmap[word[:i] + '*' + word[i+1:]].append(word)\n",
    "        q = collections.deque([beginWord])\n",
    "        #q.append(beginWord)\n",
    "        w_dict = {beginWord:[beginWord]}\n",
    "        while q:\n",
    "            word = q.popleft()\n",
    "            if word == endWord:\n",
    "                return len(w_dict[word])\n",
    "            for i in range(len(word)):\n",
    "                if word[:i] + '*' + word[i + 1:] in hashmap:\n",
    "                    for tmp in hashmap[word[:i] + '*' + word[i + 1:]]:\n",
    "                        if tmp not in w_dict:\n",
    "                            w_dict[tmp] = w_dict[word] + [tmp]\n",
    "                            q.append(tmp)\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:\n",
    "        wordList.append(beginWord)\n",
    "        buckets = defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                match = word[:i] + '_' +word[i+1:]\n",
    "                buckets[match].append(word)\n",
    "        preword = defaultdict(list)\n",
    "        toseen = deque([(beginWord,1)])\n",
    "        befound = {beginWord:1}\n",
    "        while toseen:\n",
    "            curword,level = toseen.popleft()\n",
    "            for i in range(len(beginWord)):\n",
    "                match = curword[:i] + '_' +curword[i+1:]\n",
    "                for word in buckets[match]:\n",
    "                    if word not in befound:\n",
    "                        befound[word] = level+1\n",
    "                        toseen.append((word,level+1))\n",
    "                    if befound[word] == level+1:\n",
    "                        preword[word].append(curword)\n",
    "            if endWord in befound and level+1>befound[endWord]:\n",
    "                break\n",
    "        if endWord in befound:\n",
    "            res = [[endWord]]\n",
    "            while res[0][0] != beginWord:\n",
    "                print(res)\n",
    "                res = [[word] + r for r in res for word in preword[r[0]]]\n",
    "            return len(res[0])\n",
    "        else:\n",
    "            return len([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        graph=collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                graph[word[:i]+\"*\"+word[i+1:]].append(word)\n",
    "        print(graph)\n",
    "        queue=[(beginWord,1)]\n",
    "        visit=[]\n",
    "        while queue:\n",
    "            current,level=queue.pop(0)\n",
    "            print(current,level)\n",
    "            for i in range(len(current)):\n",
    "                current_in=current[:i]+\"*\"+current[i+1:]\n",
    "                for word in graph[current_in]:\n",
    "                    if word == endWord:\n",
    "                        print(\"11\")\n",
    "                        return level+1\n",
    "                    \n",
    "                    if word not in visit :\n",
    "                        visit.append(word)\n",
    "                        \n",
    "                        queue.append((word,level+1))\n",
    "                        \n",
    "                        \n",
    "                    \n",
    "                    \n",
    "                graph[current_in]=[]  \n",
    "                \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        graph=collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                graph[word[:i]+\"*\"+word[i+1:]].append(word)\n",
    "        print(graph)\n",
    "        queue=[(beginWord,1)]\n",
    "        visit=[]\n",
    "        while queue:\n",
    "            current,level=queue.pop(0)\n",
    "            print(current,level)\n",
    "            for i in range(len(current)):\n",
    "                current_in=current[:i]+\"*\"+current[i+1:]\n",
    "                for word in graph[current_in]:\n",
    "                    if word == endWord:\n",
    "                        print(\"11\")\n",
    "                        return level+1\n",
    "                    \n",
    "                    if word not in visit :\n",
    "                        visit.append(word)\n",
    "                        \n",
    "                        queue.append((word,level+1))\n",
    "                    graph[current_in]=[]  \n",
    "                \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        graph=collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                graph[word[:i]+\"*\"+word[i+1:]].append(word)\n",
    "        print(graph)\n",
    "        queue=[(beginWord,1)]\n",
    "        visit=[]\n",
    "        while queue:\n",
    "            current,level=queue.pop(0)\n",
    "            print(current,level)\n",
    "            for i in range(len(current)):\n",
    "                current_in=current[:i]+\"*\"+current[i+1:]\n",
    "                for word in graph[current_in]:\n",
    "                    if word == endWord:\n",
    "                        print(\"11\")\n",
    "                        return level+1\n",
    "                    \n",
    "                    if word not in visit :\n",
    "                        visit.append(word)\n",
    "                        \n",
    "                        queue.append((word,level+1))\n",
    "                        \n",
    "                        \n",
    "                    \n",
    "                    \n",
    "                #graph[current_in]=[]  \n",
    "                \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]):\n",
    "        if endWord not in wordList: return 0\n",
    "\n",
    "        word_id = dict()  # 存储每个单词及其虚拟单词（简称节点）的id，key为单词或虚拟单词（即节点），value为id值\n",
    "        edge = collections.defaultdict(list)  # 存储与每个节点 相连接 的其他节点， key为源节点的id， value为目标节点的id（可有多个目标节点）\n",
    "        nodeNum = 0  # 节点 id，初始化为0\n",
    "\n",
    "        # 图构建\n",
    "        for word in [beginWord] + wordList:  \n",
    "            # 单词赋予id\n",
    "            word_id[word] = nodeNum\n",
    "            id1 = nodeNum\n",
    "            nodeNum += 1\n",
    "            # 虚拟单词赋予id，并构建边\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                new_word = \"\".join(chars)\n",
    "                # 单词的连接 就是通过具有相同的虚拟单词来间接连接\n",
    "                if new_word not in word_id:   \n",
    "                    word_id[new_word] = nodeNum\n",
    "                    nodeNum += 1\n",
    "                id2 = word_id[new_word]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1) \n",
    "                chars[i] = tmp\n",
    "\n",
    "        begin_id, end_id = word_id[beginWord], word_id[endWord]\n",
    "        dis = [float(\"inf\")] * nodeNum  # dis[i] 表示从起始单词转换到 id 为i的单词 所需的转换次数\n",
    "        dis[begin_id] = 0\n",
    "\n",
    "        # 广度优先搜索\n",
    "        que = collections.deque([begin_id])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == end_id:\n",
    "                return dis[x] // 2 +1\n",
    "            for it in edge[x]: # 遍历x所连的所有边\n",
    "                if dis[it] == float(\"inf\"):  # 因为是双向边，不加限制的话会逆回去遍历，这里就限定了没遍历过的边\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"x\n",
    "    广度优先搜索\n",
    "    关键是查找表的构建\n",
    "    \"\"\"\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        dis = [float(\"inf\")] * nodeNum\n",
    "        beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "        dis[beginId] = 0\n",
    "\n",
    "        que = collections.deque([beginId])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == endId:\n",
    "                return dis[endId] // 2 + 1\n",
    "            for it in edge[x]:\n",
    "                if dis[it] == float(\"inf\"):\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList: return 0\n",
    "\n",
    "        word_id = dict()  # 存储每个单词及其虚拟单词（简称节点）的id，key为单词或虚拟单词（即节点），value为id值\n",
    "        edge = collections.defaultdict(list)  # 存储与每个节点 相连接 的其他节点， key为源节点的id， value为目标节点的id（可有多个目标节点）\n",
    "        nodeNum = 0  # 节点 id，初始化为0\n",
    "\n",
    "        # 图构建\n",
    "        for word in [beginWord] + wordList:  \n",
    "            # 单词赋予id\n",
    "            word_id[word] = nodeNum\n",
    "            id1 = nodeNum\n",
    "            nodeNum += 1\n",
    "            # 虚拟单词赋予id，并构建边\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                new_word = \"\".join(chars)\n",
    "                # 单词的连接 就是通过具有相同的虚拟单词来间接连接\n",
    "                if new_word not in word_id:   \n",
    "                    word_id[new_word] = nodeNum\n",
    "                    nodeNum += 1\n",
    "                id2 = word_id[new_word]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1) \n",
    "                chars[i] = tmp\n",
    "\n",
    "        begin_id, end_id = word_id[beginWord], word_id[endWord]\n",
    "        dis = [float(\"inf\")] * nodeNum  # dis[i] 表示从起始单词转换到 id 为i的单词 所需的转换次数\n",
    "        dis[begin_id] = 0\n",
    "\n",
    "        # 广度优先搜索\n",
    "        que = collections.deque([begin_id])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == end_id:\n",
    "                return dis[x] // 2 +1\n",
    "            for it in edge[x]: # 遍历x所连的所有边\n",
    "                if dis[it] == float(\"inf\"):  # 因为是双向边，不加限制的话会逆回去遍历，这里就限定了没遍历过的边\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def add_word(word):\n",
    "            nonlocal words, node_id\n",
    "            if word not in words:\n",
    "                words[word] = node_id\n",
    "                node_id += 1\n",
    "        \n",
    "\n",
    "        def add_edge(word):\n",
    "            nonlocal edge\n",
    "            add_word(word)\n",
    "            idx = words.get(word)\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = '*'\n",
    "                new_word = ''.join(chars)\n",
    "                add_word(new_word)\n",
    "                idx_ = words.get(new_word)\n",
    "                edge.setdefault(idx, []).append(idx_)\n",
    "                edge.setdefault(idx_, []).append(idx)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        words = {}\n",
    "        edge = {}\n",
    "        node_id = 0\n",
    "        for word in wordList:\n",
    "            add_edge(word)\n",
    "        \n",
    "        add_edge(beginWord)\n",
    "\n",
    "        if endWord not in words:\n",
    "            return 0\n",
    "\n",
    "        dis = [inf] * node_id\n",
    "        bi, ei = words.get(beginWord), words.get(endWord)\n",
    "        dis[bi] = 0\n",
    "\n",
    "        q = [bi]\n",
    "        while q:\n",
    "            idx = q.pop(0)\n",
    "            if idx == ei:\n",
    "                return dis[ei] // 2 + 1\n",
    "            for ni in edge[idx]:\n",
    "                if dis[ni] == inf:\n",
    "                    dis[ni] = dis[idx] + 1\n",
    "                    q.append(ni)\n",
    "\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        disBegin = [float(\"inf\")] * nodeNum\n",
    "        beginId = wordId[beginWord]\n",
    "        disBegin[beginId] = 0\n",
    "        queBegin = collections.deque([beginId])\n",
    "\n",
    "        disEnd = [float(\"inf\")] * nodeNum\n",
    "        endId = wordId[endWord]\n",
    "        disEnd[endId] = 0\n",
    "        queEnd = collections.deque([endId])\n",
    "\n",
    "        while queBegin or queEnd:\n",
    "            queBeginSize = len(queBegin)\n",
    "            for _ in range(queBeginSize):\n",
    "                nodeBegin = queBegin.popleft()\n",
    "                if disEnd[nodeBegin] != float(\"inf\"):\n",
    "                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1\n",
    "                for it in edge[nodeBegin]:\n",
    "                    if disBegin[it] == float(\"inf\"):\n",
    "                        disBegin[it] = disBegin[nodeBegin] + 1\n",
    "                        queBegin.append(it)\n",
    "\n",
    "            queEndSize = len(queEnd)\n",
    "            for _ in range(queEndSize):\n",
    "                nodeEnd = queEnd.popleft()\n",
    "                if disBegin[nodeEnd] != float(\"inf\"):\n",
    "                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1\n",
    "                for it in edge[nodeEnd]:\n",
    "                    if disEnd[it] == float(\"inf\"):\n",
    "                        disEnd[it] = disEnd[nodeEnd] + 1\n",
    "                        queEnd.append(it)\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addword(word):\n",
    "            if word not in wordid:\n",
    "                nonlocal nodenum\n",
    "                wordid[word] = nodenum\n",
    "                nodenum += 1\n",
    "\n",
    "\n",
    "        def addedge(word):\n",
    "            addword(word)\n",
    "            id1 = wordid[word]\n",
    "            for i in range(len(word)):\n",
    "                newword = word[:i]+'*'+word[i+1:]\n",
    "                addword(newword)\n",
    "                id2 = wordid[newword]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "\n",
    "\n",
    "        wordid = {}\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodenum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addedge(word)\n",
    "        addedge(beginWord)\n",
    "\n",
    "        if endWord not in wordid:\n",
    "            return 0\n",
    "        \n",
    "        dis = [float('inf')]*nodenum\n",
    "        beginid, endid = wordid[beginWord], wordid[endWord]\n",
    "        dis[beginid] = 0\n",
    "\n",
    "        que = collections.deque([beginid])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            if cur == endid:\n",
    "                return dis[endid] // 2 + 1\n",
    "            for word in edge[cur]:\n",
    "                if dis[word] == float('inf'):\n",
    "                    dis[word] = dis[cur] + 1\n",
    "                    que.append(word)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        disBegin = [float(\"inf\")] * nodeNum\n",
    "        beginId = wordId[beginWord]\n",
    "        disBegin[beginId] = 0\n",
    "        queBegin = collections.deque([beginId])\n",
    "\n",
    "        disEnd = [float(\"inf\")] * nodeNum\n",
    "        endId = wordId[endWord]\n",
    "        disEnd[endId] = 0\n",
    "        queEnd = collections.deque([endId])\n",
    "\n",
    "        while queBegin or queEnd:\n",
    "            queBeginSize = len(queBegin)\n",
    "            for _ in range(queBeginSize):\n",
    "                nodeBegin = queBegin.popleft()\n",
    "                if disEnd[nodeBegin] != float(\"inf\"):\n",
    "                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1\n",
    "                for it in edge[nodeBegin]:\n",
    "                    if disBegin[it] == float(\"inf\"):\n",
    "                        disBegin[it] = disBegin[nodeBegin] + 1\n",
    "                        queBegin.append(it)\n",
    "\n",
    "            queEndSize = len(queEnd)\n",
    "            for _ in range(queEndSize):\n",
    "                nodeEnd = queEnd.popleft()\n",
    "                if disBegin[nodeEnd] != float(\"inf\"):\n",
    "                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1\n",
    "                for it in edge[nodeEnd]:\n",
    "                    if disEnd[it] == float(\"inf\"):\n",
    "                        disEnd[it] = disEnd[nodeEnd] + 1\n",
    "                        queEnd.append(it)\n",
    "        \n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        disBegin = [float(\"inf\")] * nodeNum\n",
    "        beginId = wordId[beginWord]\n",
    "        disBegin[beginId] = 0\n",
    "        queBegin = collections.deque([beginId])\n",
    "\n",
    "        disEnd = [float(\"inf\")] * nodeNum\n",
    "        endId = wordId[endWord]\n",
    "        disEnd[endId] = 0\n",
    "        queEnd = collections.deque([endId])\n",
    "\n",
    "        while queBegin or queEnd:\n",
    "            queBeginSize = len(queBegin)\n",
    "            for _ in range(queBeginSize):\n",
    "                nodeBegin = queBegin.popleft()\n",
    "                if disEnd[nodeBegin] != float(\"inf\"):\n",
    "                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1\n",
    "                for it in edge[nodeBegin]:\n",
    "                    if disBegin[it] == float(\"inf\"):\n",
    "                        disBegin[it] = disBegin[nodeBegin] + 1\n",
    "                        queBegin.append(it)\n",
    "\n",
    "            queEndSize = len(queEnd)\n",
    "            for _ in range(queEndSize):\n",
    "                nodeEnd = queEnd.popleft()\n",
    "                if disBegin[nodeEnd] != float(\"inf\"):\n",
    "                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1\n",
    "                for it in edge[nodeEnd]:\n",
    "                    if disEnd[it] == float(\"inf\"):\n",
    "                        disEnd[it] = disEnd[nodeEnd] + 1\n",
    "                        queEnd.append(it)\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import queue\n",
    "# class Solution:\n",
    "#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "#         # 判断两个字符串是否只有一个字符不同，只有一个字符不一样则连通，否则不连通\n",
    "#         def check(a, b):\n",
    "#             flag = True\n",
    "#             if len(a) != len(b):\n",
    "#                 flag = False\n",
    "#             else:\n",
    "#                 bt = 0\n",
    "#                 for i in range(len(a)):\n",
    "#                     if a[i] != b[i]:\n",
    "#                         if bt == 0:\n",
    "#                             bt = 1\n",
    "#                         else:\n",
    "#                             flag = False\n",
    "#                             break\n",
    "#                 if bt == 0:\n",
    "#                     flag = False\n",
    "#             return flag\n",
    "#         ans = 0\n",
    "#         if endWord in wordList:\n",
    "#             wl_len = len(wordList)\n",
    "#             # 表示节点[i][j]的连通性，需要几步转换， -1表示不可达\n",
    "#             dp = [[-1 for j in range(wl_len)]for i in range(wl_len)]\n",
    "#             # 先初始化，判断两个单词能否直接转换\n",
    "#             for i in range(wl_len):\n",
    "#                 for j in range(i+1,wl_len):\n",
    "#                     flag = check(wordList[i], wordList[j])\n",
    "#                     if flag:\n",
    "#                         dp[i][j] = 1\n",
    "#                         dp[j][i] = 1\n",
    "#             # beginWord 到 wordList 中每个单词的连通性\n",
    "#             dp_bg = [-1 for j in range(wl_len)]\n",
    "#             # 广度优先\n",
    "#             deque = queue.deque()\n",
    "#             # 直接连通\n",
    "#             for i in range(wl_len):\n",
    "#                 flag = check(wordList[i], beginWord)\n",
    "#                 if flag:\n",
    "#                     dp_bg[i] = 1\n",
    "#                     deque.append(i)\n",
    "#             # 记录每一个节点是否遍历过\n",
    "#             flags = [False for i in range(wl_len)]\n",
    "#             while deque:\n",
    "#                 i = deque.popleft()\n",
    "#                 flags[i] = True\n",
    "#                 # 得到i阶段与wordList中其他节点的连通情况\n",
    "#                 for j in range(wl_len):\n",
    "#                     if dp[i][j] != -1:\n",
    "#                         # beginWord 先到i, 再通过i到达j 的步数\n",
    "#                         bg_i_j = dp_bg[i] + dp[i][j]\n",
    "#                         if dp_bg[j] == -1:\n",
    "#                             dp_bg[j] = bg_i_j\n",
    "#                         else:\n",
    "#                             dp_bg[j] = min(bg_i_j, dp_bg[j])\n",
    "#                         if flags[j] is False:\n",
    "#                             deque.append(j)\n",
    "#             for i in range(wl_len):\n",
    "#                 if wordList[i] == endWord:\n",
    "#                     ans = dp_bg[i]\n",
    "#                     break\n",
    "#             ans += 1\n",
    "                \n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        dis = [float(\"inf\")] * nodeNum\n",
    "        beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "        dis[beginId] = 0\n",
    "\n",
    "        que = collections.deque([beginId])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == endId:\n",
    "                return dis[endId] // 2 + 1\n",
    "            for it in edge[x]:\n",
    "                if dis[it] == float(\"inf\"):\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "        \n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        dis = [float(\"inf\")] * nodeNum\n",
    "        beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "        dis[beginId] = 0\n",
    "\n",
    "        que = collections.deque([beginId])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == endId:\n",
    "                return dis[endId] // 2 + 1\n",
    "            for it in edge[x]:\n",
    "                if dis[it] == float(\"inf\"):\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word:str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        def  addEdge(word:str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = '*'\n",
    "                newWord = ''.join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        dis = [float(\"inf\")] * nodeNum\n",
    "        beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "        dis[beginId] = 0\n",
    "\n",
    "        que = collections.deque([beginId])\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x == endId:\n",
    "                return dis[endId] // 2 + 1\n",
    "            for it in edge[x]:\n",
    "                if dis[it] == float(\"inf\"):\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "        \n",
    "        return 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
